package com.wtgroup.demo.leetcode.org_bytedance;

/**
 *
 */
public class Q_接雨水 {

    public static void main(String[] args) {
        // int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        // int[] height = {4, 2, 0, 3, 2, 5};
        // int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int[] height = {9, 6, 8, 8, 5, 6, 3};
        Q_接雨水 exe = new Q_接雨水();
        int res = exe.trap(height);
        System.out.println(res);
    }

    /*
    * My:
    * 1. 略过开头的所有 0;
    * 2. 扫描局部最大值, >=左邻 && < 右邻.
    *   两个相邻局部最大值之间, 计算一次雨水. Math.min(左, 右) * 距离 - 中间挤掉的.
    *
    * Q: 单凭局部最大不行. right 如果有更大的局部最大, 就会少算.
    * A: right < left 时, 不用, 但留作备胎, 往后继续找 >= left 的, 如果没有找到, 才用前面的备胎
    *
    * [超出时间限制]
    * */

    public int trap(int[] height) {
        int len = height.length;
        if (len < 3) {
            return 0;
        }

        int left = nextLocalMax(height, 0);
        if (left==len) {
            return 0;
        }
        int totalArea = 0;
        // 记录最近一次可用的, 为了能往后继续找更大局部大值
        int prevRight = len;
        while (left < len) {
            int right = left;
            while (++right<len) {
                right = nextLocalMax(height, right);
                if (right==len) {
                    break;
                }
                // right >= left 才可用
                if(height[right] >= height[left]) {
                    break;
                } else {
                    // right 尽可能取大的
                    prevRight = prevRight == len || height[right] >= height[prevRight] ? right : prevRight;
                }
            }
            if (right == len && prevRight == len) {
                // 没有可用的 right
                return totalArea;
            } else if (right == len) {
                // 后面没有可用的了, 只能用上一次可用的
                right = prevRight;
            }
            // 继续置为无效, 防止后面误用
            prevRight = len;


            // 右边一个局部最大值
            int h = Math.min(height[left], height[right]);
            int area = h * (right - left - 1);
            for (int i = left+1; i <= right-1; i++) {
                area -= Math.min(h, height[i]);
            }
            totalArea += area;
            left = right;
        }

        return totalArea;
    }

    private int nextLocalMax(int[] height, int start) {
        int n = height.length;
        if (n < 3) {
            return n;
        }

        for (int i = start; i < n; i++) {
            if (i == 0) {
                if (height[i] > height[i + 1]) {
                    return i;
                }
            }
            else if (i == n - 1) {
                if (height[i] >= height[i - 1]) {
                    return i;
                }
            }
            else {
                if (height[i] >= height[i - 1] && height[i] > height[i + 1]) {
                    return i;
                }
            }
        }

        return n;
    }


}
